package me.yobol.lintcode.medium.maxprofit;

/**
 *
 * @author Yobol
 */
public class MaxProfit implements IMaxProfit {

    /**
     * 贪心算法
     * 
     * @param prices
     * @return 
     */
    @Override
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        
        //2 1 2 0 1
        //profit = 0
        //首先找到极小值（不考虑边界）1，然后找到极大值2，然后2 - 1 = 1盈利profit += 1
        //然后再往后找到极小值0，然后再找到极大值（不考虑边界）1，然后1 - 0 = 1盈利profit += 1
        //继续向后进行，直到到达数组最后（如果极大值与极小值不匹配则不加最后的极小值）
        //共盈利2
        int maxProfit = 0;//最大利润
        int profit;
        int extremeIndex = 0;//极值下标
        int counter = 0;//极值个数,counter为奇数时，下一个找到的为极大值；否则为极小值
        
        while (extremeIndex < prices.length - 1) {            
            if (counter % 2 == 0) {
                extremeIndex = indexOfNextMinExtremum(prices, extremeIndex, prices.length - 1);
            }else{
                profit = prices[extremeIndex];//极小值
                extremeIndex = indexOfNextMaxExtremum(prices, extremeIndex, prices.length - 1);//极大值下标
                profit = prices[extremeIndex] - profit;
                maxProfit += profit;
            }
            counter++;
        }
        return maxProfit;
    }
    
    //3,*3,5,0,*0,3,*1,4
    private int indexOfNextMinExtremum(int[] dst,int start,int end){
        int minExtremumIndex = start;
        for (int i = start + 1; i <= end; i++) {
            if (dst[i] <= dst[minExtremumIndex]) {
                minExtremumIndex = i;
            }else{
                break;
            }
        }
        return minExtremumIndex;
    }
    //3,3,*5,0,0,*3,1,*4
    private int indexOfNextMaxExtremum(int[] dst, int start,int end){
        int maxExtremumIndex = start;
        for (int i = start + 1; i <= end; i++) {
            if (dst[i] >= dst[maxExtremumIndex]) {
                maxExtremumIndex = i;
            }else{
                break;
            }
        }
        return maxExtremumIndex;
    }
}
